package 优先队列;

import java.util.Arrays;

public class PriorityQueueTest {

    private int[] elem;
    private int size;

    //打印
    public void display(){
        for (int i = 0; i < size; i++) {
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }
    //建堆 O（N）
    public void creatPriorityQueue(int[] arr) {
        //数组有效元素个数
        size=arr.length;
        elem=Arrays.copyOf(arr,arr.length);
        for (int parent = (size-1-1)/2; parent >=0 ; parent--) {
            siftDown(parent);
        }

    }
    //交换
    private void swap(int[]arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //向下调整 大根堆
    private void siftDown(int parent){
        //左孩子
        int child=parent*2+1;
        while (child<size){
            if(child+1<size&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
               //交换
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    private boolean isFull(){
        if(size>=elem.length){
            return true;
        }
        return false;
    }
    //向上调整
    private void siftUp(int e){
        int child=size;
        elem[child]=e;
        while (child>0){
            int parent=(child-1)/2;
            //大根堆
            if(elem[parent]<elem[child]){
                swap(elem,parent,child);
                child=parent;
            }else{
                break;
            }
        }
    }
    //入队  O(log2n)
    public boolean offer(int e){
        if(isFull()){
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        siftUp(e);
        size++;
        return true;
    }

    //看队头
    public int peek(){
        return elem[0];
    }
    //出队 O(log2n)
    public int poll(){
        if(size==0)return -1;
        int old=elem[0];
        swap(elem,0,size-1);
        size--;
        //0下标向下调整
        siftDown(0);
        return old;
    }
    //大小
    public int size(){
        return size;
    }
    //清空
    public void clear(){
        size=0;
    }
    //判空
    public boolean isEmpty(){
        if(size==0)return true;
        return false;
    }

    //向下调整 大根堆
    private void siftDown(int parent,int len) {
        //左孩子
        int child=parent*2+1;
        while (child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                //交换
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //从小到大排序 大根堆
    public void heapSort(){
        //记录替换的下标
        int end=size-1;
        while (end>0){
            //替换
            swap(elem,end,0);
            //向下调整 要重新定义边界，因为后面的元素有序了
            siftDown(0,end);
            end--;
        }
    }
    //向下调整 小根堆
    private void siftDown1(int parent,int len) {
        //左孩子
        int child=parent*2+1;
        while (child<len){
            if(child+1<len&&elem[child]>elem[child+1]){
                child++;
            }
            if(elem[child]<elem[parent]){
                //交换
                swap(elem,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }
    //从大到小排序 小根堆
    public void heapSort1(){
        //记录替换的下标
        int end=size-1;
        while (end>0){
            //替换
            swap(elem,end,0);
            //向下调整 要重新定义边界，因为后面的元素有序了
            siftDown1(0,end);
            end--;
        }
    }
}
